//给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
//
//
//
//
//
// 示例 1：
//
//
//输入：n = 3
//输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：[[1]]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 8
//
//
//
// Related Topics 树 二叉搜索树 动态规划 回溯 二叉树 👍 1264 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * [P95]_不同的二叉搜索树 II
 * @author cjl
 * @date 2022-07-24 15:51:25
 */
public class P95_UniqueBinarySearchTreesIi{
      public static void main(String[] args) {
            //测试代码
           Solution solution = new P95_UniqueBinarySearchTreesIi().new Solution();
      }
      //力扣代码
      //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 分别构建左子树和右子树，然后组合；
     * @param n
     * @return
     */
    public List<TreeNode> generateTrees(int n) {
        if(n == 0){
            return new ArrayList<>();
        }
        return buidTree(1, n);
    }

    public List<TreeNode> buidTree(int start, int end){
        List<TreeNode> resList = new ArrayList<>();
        if(start > end){
            resList.add(null);
            return resList;
        }
        for(int i = start ; i <= end ; i++){
            //生成所有左子树
            List<TreeNode> leftList = buidTree(start, i-1);
            //生成所有右子树
            List<TreeNode> rightList = buidTree(i+1 ,end);
            //组合所有可能的tree
            for(TreeNode left: leftList){
                for(TreeNode right: rightList){
                    TreeNode treeNode = new TreeNode(i , left, right);
                    resList.add(treeNode);
                }
            }
        }
        return resList;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

  }